package edu.uaskl.jqf.model.math;

import java.util.ArrayList;
import java.util.List;

import edu.uaskl.jqf.tools.MathTools;

/**
 * Represents a (simple) continued fraction.
 * 
 * Example:<br>
 * 73.0 / 11 is [6, 1, 1, 1, 3].<br>
 * Because 73.0/11 is 6 + 1/(1 + 1/(1 + 1/(1 + 1/3)))<br>
 * <br>
 * General form:<br>
 * x/y is [a0, a1, ..., an]<br>
 * Because there exists a0 in Z and a1, ..., an in N such that x/y = a0 + 1/(a0 + 1/(a2 + ... + 1/an)) for any x,y in Z<br>
 * <br>
 * There are exactly two ways to represent a continued fraction:<br>
 * [a0, a1, ..., a(n-1), an, 1] = [a0, a1, ..., a(n-1), an + 1] We use the shorter one<br>
 * <br>
 * More information: <br>
 * <a href="http://mathworld.wolfram.com/SimpleContinuedFraction.html">http://mathworld.wolfram.com/SimpleContinuedFraction.html</a><br>
 * <a href="http://mathworld.wolfram.com/ContinuedFraction.html">http://mathworld.wolfram.com/ContinuedFraction.html</a><br>
 * <a href="http://en.wikipedia.org/wiki/Continued_fraction">http://en.wikipedia.org/wiki/Continued_fraction</a><br>
 * <br>
 * Implementation note: To save a Fraction class, this class does not provide a static method to get the fraction for a number.<br>
 * Create new instance and use {@link #getNumerator()} and {@link #getDenominator()} to get them.<br>
 * 
 * @author tbach
 */
public class ContinuedFraction {
    private Double number; // Double instead of double, so we can check for null. This needs autoboxing later on, but we dont care -tbach
    private List<Long> continuedFractionList;
    private Long numerator; // numerator/denominator -tbach
    private Long denominator;

    public ContinuedFraction(final Double number) {
        if (Double.isNaN(number) || Double.isInfinite(number))
            throw new IllegalArgumentException("Not a valid Argument: " + number);
        this.number = number;
    }

    public ContinuedFraction(final List<Long> continuedFractionList) {
        if (continuedFractionList.size() == 0) // throws NPE, so we do not have to check for null here -tbach
            throw new IllegalArgumentException("Fraction list cannot be empty");
        this.continuedFractionList = continuedFractionList;
    }

    public double getNumber() {
        if (number == null)
            if ((numerator != null) & (denominator != null))
                number = (1.0 * numerator) / denominator;
            else if (continuedFractionList != null)
                number = getNumberFromContinuedFractionList(continuedFractionList);
            else
                throw new IllegalStateException("Cannot calculate number, no fraction or continued fraction set");
        return number;
    }

    /**
     * Converts a continued fraction list into a double number.<br>
     * Example:<br>
     * 73.0 / 11 is [6, 1, 1, 1, 3].<br>
     * Input: [6, 1, 1, 1, 3]<br>
     * Return: 6.636363636363637 (=73.0 / 11)<br>
     * 
     * @param continuedFractionList
     *            The list of continued fractions, assuming long items.
     * @return The converted number
     */
    public static double getNumberFromContinuedFractionList(final List<Long> continuedFractionList) {
        if (continuedFractionList.size() == 0) // throws NPE, so we do not have to check for null here -tbach
            return 0;
        double result = continuedFractionList.get(continuedFractionList.size() - 1);
        for (int i = continuedFractionList.size() - 2; i >= 0; --i) {
            final long item = continuedFractionList.get(i);
            result = item + (1.0 / result);
        }
        return result;
    }

    public List<Long> getContinuedFractionList() {
        if (continuedFractionList == null)
            continuedFractionList = getContinuedFractionExpansionFromNumber(getNumber());
        return continuedFractionList;
    }

    /** Argument must not be NaN or infinite */
    public static List<Long> getContinuedFractionExpansionFromNumber(final double number) {
        if (Double.isNaN(number) || Double.isInfinite(number))
            throw new IllegalArgumentException("Not a valid Argument: " + number);
        // See an example: http://en.wikipedia.org/wiki/Continued_fraction#Calculating_continued_fraction_representations
        final List<Long> result = new ArrayList<>();
        double rest = number;
        while (Math.abs(rest - Math.round(rest)) >= MathTools.EPSILON) { // a bit nasty, but will do the job for finite continued fractions -tbach
            final long integer = (long) rest;
            result.add(integer); // this will break with out of memory for infinite continued fractions (which should not happen, because FP is finite) -tbach
            rest = 1 / (rest - integer);
        }
        result.add(Math.round(rest));
        return result;
    }

    public Long getNumerator() {
        if (numerator == null)
            calculateAndSetNumeratorAndDenominator();
        return numerator;
    }

    public Long getDenominator() {
        if (denominator == null)
            calculateAndSetNumeratorAndDenominator();
        return denominator;
    }

    private void calculateAndSetNumeratorAndDenominator() {
        final List<Long> myContinuedFractionList = getContinuedFractionList();
        long myNumerator = 1;
        long myDenominator = myContinuedFractionList.get(myContinuedFractionList.size() - 1);

        for (int i = myContinuedFractionList.size() - 2; i >= 0; --i) {
            final long item = myContinuedFractionList.get(i);

            // we have 1/(ai + 1/a(i+1)). So we make LCD, add and change numerator and denominator -tbach
            final long currentDenominator = myDenominator;
            myDenominator = (item * currentDenominator) + myNumerator;
            myNumerator = currentDenominator;
        }
        final long currentDenominator = myDenominator;
        myDenominator = myNumerator;
        myNumerator = currentDenominator;

        numerator = myNumerator;
        denominator = myDenominator;
    }

    @Override
    public String toString() {
        final StringBuilder builder = new StringBuilder();
        builder.append("ContinuedFraction [number=");
        builder.append(getNumber());
        builder.append(", continuedFractionList=");
        builder.append(getContinuedFractionList());
        builder.append(", numerator=");
        builder.append(getNumerator());
        builder.append(", denominator=");
        builder.append(getDenominator());
        builder.append("]");
        return builder.toString();
    }
}
